package collections;

/**
 * 实现一个简单HashMap<int, int>
 *     实现add / get / remove方法
 *     leetcode https://leetcode.cn/problems/design-hashmap/description/
 *     只处理正数
 */
public class MyHashMap {
    int size = 0;
    int capacity = 8;
    // 节点类
    class Entry {
        int key;
        int value;
        Entry next;
        Entry(int k, int v) {
            key = k;
            value = v;
        }
    }
    Entry[] bucket;

    public MyHashMap() {
        bucket = new Entry[capacity];
    }

    public void put(int key, int value) {
        Entry entry = new Entry(key, value);
        int index = key % capacity;
        // slot为空
        if(bucket[index] == null){
            bucket[index] = entry;
            size++;
        }
        else {
            // 从头开始找，找不到就插入，找到就修改
            Entry prev = bucket[index];
            if(prev.key == key){
                prev.value = value;
                return;
            }
            while(prev.next != null) {
                if(prev.next.key == key) {
                    prev.next.value = value;
                    return;
                }
                prev = prev.next;
            }
            prev.next = entry;
            size++;
        }
    }

    public int get(int key) {
        int index = key % capacity;
        if(bucket[index] == null) return -1;
        Entry cur = bucket[index];
        while(cur != null) {
            if(cur.key == key) {
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }

    public void remove(int key) {
        int index = key % capacity;
        if(bucket[index] == null) return;
        Entry cur = bucket[index];
        // 如果是头节点特殊处理
        if(cur.key == key) {
            Entry newHead = cur.next;
            // gc
            cur.next = null;
            bucket[index] = newHead;
            size--;
            return;
        }

        // 不是头结点再去找
        while(cur.next != null) {
            if(cur.next.key == key) {
                Entry removed = cur.next;
                cur.next = removed.next;
                // gc
                removed.next = null;
                size--;
                return;
            }
            cur = cur.next;
        }
    }

    // 测试
    public static void main(String[] args) {
        MyHashMap myHashMap = new MyHashMap();
        myHashMap.put(1, 1);
        myHashMap.put(2, 2);
        myHashMap.put(9, 9);
        System.out.println(myHashMap.get(1));
        System.out.println(myHashMap.get(2));
        System.out.println(myHashMap.get(9));
        System.out.println(myHashMap.get(3)); // not found
        myHashMap.put(2, 4); // update
        System.out.println(myHashMap.get(2));
        myHashMap.remove(2);
        System.out.println(myHashMap.get(2));
        myHashMap.put(33, 87);
        myHashMap.remove(33);
        System.out.println(myHashMap.get(33));
    }
}

